//王润辉
//1200018504
// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 在此，我感谢 刘洪轩,胡树伟对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
//
//    <刘洪轩 刘当一 胡树伟 王润辉>
//    我的eclat算法是刘当一的Apriori的程序的基础上改进的，程序的框架是借鉴的他的，具体实现是自己完成的，后期的一些优化是在刘洪轩的帮助下完成的。
#include <iostream>
#include <cassert>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <iterator>
#include <cstring>
using namespace std;
bool quiet = false;
class setOfItem
{
public:
	int countTrans;
	vector<bool> numOfTrans;
	vector<int> Item;
}items[20000];//数组大小是根据输入数据决定的, 用来存所有项及包含此项的交易编号
void apriori(istream& file, ostream& output, double threshold)
{
	int n = 0, m;					//n: 物品数量，m: 交易数量
	int min_support, k = 1;				//k: 项集大小
	int all = 0;					//记录满足要求的项集数量
	string tmp_str;
	vector<setOfItem> sets;
	vector<setOfItem> setsOfNextK;
	int index = 0;//记录交易的编号
	//从文件中读取信息
	vector<vector<int> > origin_data;
	while (getline(file, tmp_str)) 
	{
		stringstream str(tmp_str);
		origin_data.push_back(vector<int>(istream_iterator<int>(str), istream_iterator<int>()));
	}//cerr << threshold*origin_data.size() << endl;
	for ( vector<vector<int> >::iterator it = origin_data.begin(); it != origin_data.end(); it ++)
	{	
		for ( vector<int>::iterator it2 = (*it).begin(); it2 != (*it).end(); it2 ++)
		{
			if (*it2 + 1 > n) n = *it2 + 1; 
		}			
	}
	m = origin_data.size();
	for ( int i = 0; i < n; ++i)
	{
		items[i].Item.push_back(i);
		items[i].numOfTrans.reserve(m);
		items[i].numOfTrans.resize(m);
		items[i].countTrans = 0;
	}
	for ( vector<vector<int> >::iterator it = origin_data.begin(); it != origin_data.end(); it ++)
	{	//记下标号为numOfItem的物品在交易index中出现（index从零开始计数）
		for ( vector<int>::iterator it2 = (*it).begin(); it2 != (*it).end(); it2 ++)
		{
			if (items[*it2].numOfTrans[index] == 0) {
				items[*it2].numOfTrans[index] = 1;
				++items[*it2].countTrans;
			}
		}			
		index ++;//更新交易编号
	}
	//寻找一维项集
	min_support = threshold * origin_data.size();
	for ( int i = 0; i < n; i ++)
	{
		if ( items[i].countTrans >= min_support)
		{
			all ++;
			sets.push_back(items[i]);
			if (!quiet)
			output << items[i].Item[0] << " : " << items[i].countTrans << endl;
		}
	}
	//由k维项集生成k+1维项集
	while (!sets.empty())
       	{
		k ++;	
		for (vector<setOfItem>::iterator it = sets.begin(); it != sets.end(); it++)
	       	{
			for (vector<setOfItem>::iterator it2 = it + 1; it < sets.end() && it2 < sets.end(); it2++) 
			{
				for (int i = 0; i < k-2; i++) 
				{
					if (it->Item[i] != it2->Item[i]) 
					{
						goto loopEnd;
					}
				}
				vector<int> array_int = it->Item;
				array_int.push_back(it2->Item[k-2]);
				vector<bool> tmp;
				int tmpcountTrans = 0;
				tmp.reserve(m);
				tmp.resize(m);
				for ( int i = 0; i < m; i ++) {
					tmp[i] = it->numOfTrans[i] & it2->numOfTrans[i];
					if (tmp[i] == 1) ++tmpcountTrans;
				}
				if ( tmpcountTrans >= min_support)
				{
					all ++;
					setOfItem t;
					t.Item.swap(array_int);
					assert (t.Item.size() > 0);
					t.numOfTrans.swap(tmp);
					t.countTrans = tmpcountTrans;
					setsOfNextK.push_back(t);
					index ++;
					if (!quiet)
					{
						for ( int i = 0; i < k; i ++)
							output << t.Item[i] <<' ';
						output << ':' << ' ' << t.countTrans << endl;
					}
				}
			}
		loopEnd:
			;
		}
		sets.swap(setsOfNextK);
		setsOfNextK.clear();
	}
	if (quiet)
		output << all << endl;//输出项集个数
}
int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);
	if (argc > 2 && strcmp(argv[2],"-q") == 0)
		quiet = true;
	apriori(cin, cout, atof(argv[1]));
	return 0;
}
